package leetcode;
/**
 * 剑指OfferⅡ 077.链表排序
 * 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 */
public class Offer_077 {
    /** 创建新的链表 **/
    public ListNode sortList(ListNode head) {
        //head为空的情况
        if(head == null){
            return head;
        }
        //创建一个虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        //先把head的第一个节点接在新链表后面
        dummyHead.next = new ListNode(head.val);
        //从head的第二个节点开始遍历，以升序的方式插入新链表中
        head = head.next;
        while(head != null){
            //每次插入一个新的节点，都从新链表的头开始遍历，找合适的位置
            ListNode prev = dummyHead;
            while(prev.next != null){
                if(prev.next.val >= head.val){
                    //到达拼接位置,结束这层循环
                    break;
                }else{
                    //prev向后移动一位，继续比较
                    prev = prev.next;
                }
            }
            //拼接node
            ListNode node = new ListNode(head.val);
            node.next = prev.next;
            prev.next = node;
            //head向后移动一位，接着遍历旧链表
            head = head.next;
        }
        return dummyHead.next;
    }
}
